package com.ch.贪心;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author chenhong
 * @version 1.0.0
 * @ClassName N406.java
 * @Description TODO
 * @createTime 2021年07月09日 11:08:00
 */
public class N406 {
    public static void main(String[] args) {
        int[][] people = {{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}};
        Solution406 solution406 = new Solution406();
        int[][] ans = solution406.reconstructQueue(people);
        System.out.println(ans);
    }


}
class Solution406 {
    public int[][] reconstructQueue(int[][] people) {
        int n = people.length;
        int m = people[0].length;
        if (n == 0 || m == 0) {
            return new int[0][0];
        }

        Arrays.sort(people, new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {

                // 先按身高降序，若身高相同则按 k 值升序。
                return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
            }
        });

        // 遍历排序后的数组，根据 K 插入到 K 的位置上。矮的对高的没影响，所以如果有两个人在相同位置，
        // k值相同，但是矮的后插入，后来居上，但是对高的没影响，高的前面的k个>=仍未k个
        List<int[]> list = new ArrayList<>();
        for (int[] p : people) {

            list.add(p[1], p);
        }
        return list.toArray(new int[list.size()][2]);
    }
}